using System;
using System.Diagnostics;
using FineCollection.Intf;



namespace FineCollection.Const
{

    public static partial class CC
    {


        #region LIST OF


        /// <summary>
        /// Makes a constant list with one specified item.
        /// </summary>
        /// <typeparam name="T">item type.</typeparam>
        /// <param name="firstIndex">first index (indexing origin).</param>
        /// <param name="item">the item that will be in the constant list.</param>
        /// <returns>just created constant list.</returns>
        public static ConstList<T> ListOf<T>(int firstIndex, T item)
        {
            T[] theArray = new [] {item};
            return new ConstList<T>(firstIndex, theArray, 1, true);
        }


        /// <summary>
        /// Makes a list of the specified items,
        /// preserving their order.
        /// </summary>
        /// <typeparam name="T">items type.</typeparam>
        /// <param name="firstIndex">first index (indexing origin).</param>
        /// <param name="items">items to make a list of.</param>
        /// <returns>the constant list with the specified items.</returns>
        public static ConstList<T> ListOf<T>(int firstIndex, params T[] items)
        {
            return new ConstList<T>(firstIndex, items, items.Length, false);
        }


        /// <summary>
        /// Makes a constant copy of the given list.
        /// </summary>
        /// <typeparam name="T">items type.</typeparam>
        /// <param name="firstIndex">first index (indexing origin).</param>
        /// <param name="list">list to make a copy of.</param>
        /// <returns>constant list.</returns>
        public static ConstList<T> ListOf<T>(int firstIndex, RCollection<T> list)
        {
            if (list == null || list.IsEmpty)
                return new ConstZeroList<T>(firstIndex);

            ConstArray<T> constArray = list as ConstArray<T>;

            if (constArray != null && constArray.firstIndex != firstIndex)
                constArray = new ConstList<T>(firstIndex, constArray);

            if (constArray == null)
            {
                T[] array = list.ToArray();
                constArray = new ConstList<T>(firstIndex, array, array.Length, true);
            }

            return constArray.ToList();
        }


        /// <summary>
        /// Makes a list of items copying them from an array.
        /// </summary>
        /// <typeparam name="T">items type.</typeparam>
        /// <param name="firstIndex">first index (indexing origin).</param>
        /// <param name="items">the array to copy items from.</param>
        /// <param name="offset">offset in array to start copy items with (zero bazed).</param>
        /// <param name="count">count of items to copy.</param>
        /// <returns>the constant list with the copied items.</returns>
        public static ConstList<T> ListOf<T>(int firstIndex, T[] items, int offset, int count)
        {
            T[] theArr = new T[count];
            Array.Copy(items, offset, theArr, 0, count);
            return new ConstList<T>(firstIndex, theArr, count, true);
        }


        #endregion



        #region SET OF 

        /// <summary>
        /// Sorts the specified items and returns an appropriate ordered set.
        /// </summary>
        /// <typeparam name="T">type of a collection item.</typeparam>
        /// <param name="firstIndex">first index (indexing origin).</param>
        /// <param name="items">array of items. Can be empty or even null.</param>
        /// <returns>the created set.
        ///     <para>
        ///        If the given argument is null, it returns null.
        ///        If the given argument is empty array it returns an empty set.
        ///     </para>
        /// </returns>
        public static ConstSortSet<T> SortSetOf<T>(int firstIndex, params T[] items)
            where T: IComparable<T>
        {
            if (items == null)
                return null;

            int n = items.Length;
            switch (n)
            {
                case 0:
                    return new ConstZeroOrderSet<T>(firstIndex);
                default:
                    return new ConstSortSet<T>(firstIndex, items, items.Length, true, true, false);
            }
        }


        /// <summary>
        /// Makes a constant sorted set by already ordered set.
        /// </summary>
        /// <typeparam name="T">type of a collection item.</typeparam>
        /// <param name="firstIndex">first index (indexing origin).</param>
        /// <param name="set">set to makes copy of.</param>
        /// <returns>constant sorted set.</returns>
        public static ConstSortSet<T> SortSetOf<T>(int firstIndex, ROrderSet<T> set)
            where T : IComparable<T>
        {
            ConstSortSet<T> constSet = set as ConstSortSet<T>;

            if (constSet != null && constSet.firstIndex != firstIndex)
            {
                constSet = new ConstSortSet<T>(firstIndex, constSet.arr, constSet.count, false, false, true);
            }

            if (constSet == null)
            {
                T[] array = set.ToArray();
                constSet = new ConstSortSet<T>(firstIndex, array, array.Length, false, false, true);
            }

            return constSet;
        }


        /// <summary>
        /// Makes a constant hash set for the specified items.
        /// </summary>
        /// <typeparam name="T">type of a collection item.</typeparam>
        /// <param name="firstIndex">first index (indexing origin).</param>
        /// <param name="items">array of items. Can be empty but not null.</param>
        /// <returns>the created set.</returns>
        public static ConstHashSet<T> HashSetOf<T>(int firstIndex, params T[] items)
        {
            Debug.Assert(items != null);
            return new ConstHashSet<T>(firstIndex, items, items.Length, true, false);
        }


        /// <summary>
        /// Makes a constant hash set for the specified items.
        /// </summary>
        /// <typeparam name="T">type of a collection item.</typeparam>
        /// <param name="firstIndex">first index (indexing origin).</param>
        /// <param name="collection">collection of items. Can be empty but not null.</param>
        /// <returns>the created set.</returns>
        public static ConstHashSet<T> HashSetOf<T>(int firstIndex, RCollection<T> collection)
        {
            Debug.Assert(collection != null);

            ConstArray<T> ca = collection as ConstArray<T>;
            if (ca != null)
            {
                if (ca is ConstHashSet<T> && ca.firstIndex == firstIndex)
                    return (ConstHashSet<T>)ca; 
                else 
                    return new ConstHashSet<T>(firstIndex, ca.arr, ca.count, !(ca is RSet<T>), false);
            }

            return new ConstHashSet<T>(firstIndex, 
                                       collection.ToArray(), collection.Count, 
                                       true, true);
        }


        #endregion



        #region BINARY OPERATIONS


        /// <summary>
        /// Concatenates two lists.
        /// </summary>
        /// <typeparam name="T">items type.</typeparam>
        /// <param name="firstIndex">first index (indexing origin).</param>
        /// <param name="listA">first list.</param>
        /// <param name="listB">second list.</param>
        /// <returns>list fo items form the firts list and from the second list.</returns>
        /// <remarks>
        /// You can use also operator <b>+</b>.
        /// </remarks>
        public static ConstList<T> Concat<T>(int firstIndex, ConstList<T> listA, ConstList<T> listB)
        {
            int nA = listA.count, nB = listB.count;
            if (nA != 0 && nB != 0)
            {
                int n = nA + nB;
                T[] array = new T[n];
                for (int i = 0; i < nA; i++)
                    array[i] = listA.arr[i];
                for (int i = 0; i < nB; i++)
                    array[nA + i] = listB.arr[i];
                return new ConstList<T>(firstIndex, array, n, true);
            }
            else if (nA != 0)
            {
                return listA;
            }
            else if (nB != 0)
            {
                return listB;
            }
            else
            {
                return new ConstZeroList<T>(firstIndex);
            }
        }


        /// <summary>
        /// Performs the union of the two ordered sets.
        /// </summary>
        /// <typeparam name="T">type of an item.</typeparam>
        /// <param name="firstIndex">first index (indexing origin).</param>
        /// <param name="set1">the first set (can be null or empty).</param>
        /// <param name="set2">the second set (can be null or empty).</param>
        /// <returns>constant union of the specified sets.</returns>
        /// <remarks>
        /// <para>
        /// The result set will contain all items that are present in both sets.
        /// So, the number of result items will be from <i>max(n1,n2)</i> to <i>n1 + n2</i>
        /// inclusive.
        /// </para>
        /// <para>
        /// This function implements a sorted merge algorithm (without sort -
        /// both sets are already ordered), 
        /// and the complexity of this method id <i>o(n)</i>,
        /// where <i>n</i> is a number of items in both sets.
        /// </para>
        /// <para>
        /// In case when one set includes another one, and the largest one
        /// is constant and ordered, this function returns the first one
        /// without making a copy.
        /// </para>
        /// </remarks>
        public static ConstSortSet<T> Union<T>(int firstIndex, ROrderSet<T> set1, ROrderSet<T> set2)
            where T: IComparable<T>
        {
            int n1 = set1 != null ? set1.Count : 0,
                n2 = set2 != null ? set2.Count : 0;

            if (n1 == 0 && n2 == 0)
            {
                return new ConstZeroOrderSet<T>(firstIndex);
            }
            else if (n1 > 0 && n2 == 0)
            {
                return SortSetOf(firstIndex, set1);
            }
            else if (n2 > 0 && n1 == 0)
            {
                return SortSetOf(firstIndex, set2);
            }
            else
            {
                return Merge(firstIndex, set1, set2);
            }

        }


        private static ConstSortSet<T> Merge<T>(int firstIndex, ROrderSet<T> set1, ROrderSet<T> set2)
            where T : IComparable<T>
        {
            int n1 = set1.Count,
                n2 = set2.Count;
            int limit = n1 + n2,
                k = 0;

            T[] arr = new T[limit];

            RIterator<T> it1 = set1.TakeIterator(),
                         it2 = set2.TakeIterator();
            bool ex1 = it1.Next(),
                 ex2 = it2.Next();
            
            while (ex1 && ex2)
            {
                int z = Math.Sign( it1.Current.CompareTo(it2.Current) );
                switch (z)
                {
                    case -1:
                        arr[k++] = it1.Current;
                        ex1 = it1.Next();
                        break;
                    case +1:
                        arr[k++] = it2.Current;
                        ex2 = it2.Next();
                        break;
                    case 0:
                        arr[k++] = it1.Current;
                        ex1 = it1.Next();
                        ex2 = it2.Next();
                        break;
                }
            }

            while (ex1)
            {
                arr[k++] = it1.Current;
                ex1 = it1.Next();
            }

            while (ex2)
            {
                arr[k++] = it2.Current;
                ex2 = it2.Next();
            }

            if (k == n1)
            {
                var constSet1 = set1 as ConstSortSet<T>;
                if (constSet1 != null && constSet1.firstIndex == firstIndex)
                    return constSet1;
            }

            if (k == n2)
            {
                var constSet2 = set2 as ConstSortSet<T>;
                if (constSet2 != null && constSet2.firstIndex == firstIndex)
                    return constSet2;
            }

            return new ConstSortSet<T>(firstIndex, arr, k, false, false, true);
        }


        /// <summary>
        /// Performs the intersection of two ordered sets.
        /// </summary>
        /// <typeparam name="T">type of an item.</typeparam>
        /// <param name="firstIndex">first index (indexing origin).</param>
        /// <param name="set1">the first set (can be null or empty).</param>
        /// <param name="set2">the second set (can be null or empty).</param>
        /// <returns>constant intersection of the specified sets.</returns>
        /// <remarks>
        /// <para>
        /// The result is a set where each item presents in both specified sets.
        /// So, the number of result items will be from <i>0</i> to <i>min(n1, n2)</i>
        /// inclusive.
        /// </para>
        /// <para>
        /// This method implements the optimized nested-loops with binary serach algorithm.
        /// Its complexity is <i>o( (m + 2) ln(n1 + n2) )</i>, where <i>m</i> is a number
        /// of items in the result set.
        /// </para>
        /// <para>
        /// In case when one set includes another one, and the largest one
        /// is constant and ordered, this function returns the first one
        /// without making a copy.
        /// </para>
        /// </remarks>
        public static ConstSortSet<T> Intersect<T>(int firstIndex, ROrderSet<T> set1, ROrderSet<T> set2)
            where T : IComparable<T>
        {
            int n1 = set1 != null ? set1.Count : 0,
                n2 = set2 != null ? set2.Count : 0;

            if (n1 == 0 || n2 == 0)
                return new ConstZeroOrderSet<T>(firstIndex);

            return FastJoin(firstIndex, set1, set2);
        }


        private static ConstSortSet<T> FastJoin<T>(int firstIndex, ROrderSet<T> set1, ROrderSet<T> set2)
            where T : IComparable<T>
        {
            int n1 = set1.Count,
                n2 = set2.Count;
            int limit = Math.Min(n1, n2),
                rn = 0;
            
            T[] resultArray = null;

            // inner join

            ROrderIterator<T> it1 = set1.TakeIterator(),
                              it2 = set2.TakeIterator();
            it1.Next();
            it2.Next();

            while (it1.Where < +1 && it2.Where < +1) // while both are active
            {
                int z = Math.Sign( it1.Current.CompareTo(it2.Current) );
                switch(z)
                {
                    case 0:
                        if (resultArray == null)
                            resultArray = new T[limit];
                        resultArray[rn++] = it1.Current;
                        it1.Next();
                        it2.Next();
                        break;

                    case -1:
                        it1.Jump(it2.Current);
                        break;

                    case +1:
                        it2.Jump(it1.Current);
                        break;
                }
            }

            if (rn == n1)
            {
                var constSet1 = set1 as ConstSortSet<T>;
                if (constSet1 != null && constSet1.firstIndex == firstIndex)
                    return constSet1;
            }

            if (rn == n2)
            {
                var constSet2 = set2 as ConstSortSet<T>;
                if (constSet2 != null && constSet2.firstIndex == firstIndex)
                    return constSet2;
            }

            return new ConstSortSet<T>(firstIndex, resultArray, rn, false, false, true);
        }



        /// <summary>
        /// Performs the mathematical difference between the <c>minuend</c> 
        /// and the <c>subtrahend</c>. In other words, this functions returns 
        /// the set contains items from the <c>minuend</c> that don't present
        /// in the <c>subtrahend</c>.
        /// </summary>
        /// <typeparam name="T">type of an item.</typeparam>
        /// <param name="firstIndex">first index (indexing origin).</param>
        /// <param name="minuend">minuend of a difference.</param>
        /// <param name="subtrahend">subtrahend of a difference.</param>
        /// <returns>the difference.</returns>
        public static ConstSortSet<T> Difference<T>(int firstIndex, ROrderSet<T> minuend, ROrderSet<T> subtrahend)
            where T : IComparable<T>
        {
            int n1 = minuend != null ? minuend.Count : 0,
                n2 = subtrahend != null ? subtrahend.Count : 0;
            
            if (n1 == 0)
                return new ConstZeroOrderSet<T>(firstIndex);

            if (n2 == 0)
            {
                if (minuend is Constant && minuend is RRandomSet<T>)
                    return SortSetOf(firstIndex, minuend);
                else
                    return SortSetOf(firstIndex, minuend);
            }

            Debug.Assert(minuend != null);
            Debug.Assert(minuend.IsNotEmpty);
            Debug.Assert(subtrahend != null);
            Debug.Assert(subtrahend.IsNotEmpty);
            

            // left anti-join

            int rn = 0;
            T[] diffArray = new T[n1];

            ROrderIterator<T> it1 = minuend.TakeIterator();
            ROrderIterator<T> it2 = subtrahend.TakeIterator();
            it1.Next();
            it2.Next();

            while (it1.Where < +1 && it2.Where < +1) // while both are active
            {
                int z = Math.Sign(it1.Current.CompareTo(it2.Current));
                switch (z)
                {
                    case 0:
                        it1.Next();
                        it2.Next();
                        break;

                    case -1:
                        diffArray[rn++] = it1.Current;
                        it1.Next();
                        break;

                    case +1:
                        it2.Jump(it1.Current);
                        break;
                }
            }

            return new ConstSortSet<T>(firstIndex, diffArray, rn, false, false, true);
        }


        #endregion



        #region CONVERTING

        /// <summary>
        /// Selects items of type <c>T2</c> from the collection with items of type <c>T1</c>.
        /// </summary>
        /// <typeparam name="T2">type of desired items, must be a subtype of <c>T1</c>.</typeparam>
        /// <typeparam name="T1">type of collection's items.</typeparam>
        /// <param name="firstIndex">first index (indexing origin).</param>
        /// <param name="col">collection to select from.</param>
        /// <returns>list of found items; the order of them is the same 
        ///          as provided by the given collection iterator.</returns>
        public static RRandomList<T2> ListByType<T2,T1>(int firstIndex, RCollection<T1> col)
            where T1: class
            where T2: class, T1
        {
            // first loop - count 
            int n = 0;
            RIterator<T1> it = col.TakeIterator();
            while (it.Next())
                if (it.Current is T2)
                    n++;

            // make appropriate copy
            ConstList<T2> result;
            switch (n)
            {
                case 0:
                    result = new ConstZeroList<T2>(firstIndex);
                    break;

                case 1:
                    RIterator<T1> it1 = col.TakeIterator();
                    T2 obj = null;
                    while (it1.Next() && obj == null)
                        if (it1.Current is T2)
                            obj = it1.Current as T2;
                    result = new ConstList<T2>(firstIndex, obj);
                    break;

                default:
                    T2[] arr = new T2[n];
                    int k = 0;
                    RIterator<T1> it2 = col.TakeIterator();
                    while (it2.Next() && k < n)
                        if (it2.Current is T2)
                            arr[k++] = it2.Current as T2;
                    result = new ConstList<T2>(1, arr, n, true);
                    break;
            }

            // ok
            return result;
        }


        #endregion


    }


}